﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/check-if-n-and-its-double-exist/
/*
题目描述：
给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。
更正式地，检查是否存在两个下标 i 和 j 满足：
	i != j
	0 <= i, j < arr.length
	arr[i] == 2 * arr[j]

示例 1：
输入：arr = [10,2,5,3]
输出：true
解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。

示例 2：
输入：arr = [7,1,14,11]
输出：true
解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。

示例 3：
输入：arr = [3,1,7,11]
输出：false
解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。
 

提示：
2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3
*/

// 方法1——暴力法
/*
思路：
直接遍历数组中的每个元素，对于每一个元素，都在遍历一次数组中除自身之外的所有元素
看看是否有刚好是自己两倍的元素。
若有，就直接返回true，若没有则继续遍历下一个元素。
如果所有元素都遍历完了也没有找到，就返回false
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
bool checkIfExist1(int* arr, int arrSize) {
	assert(arr);
	int i = 0;
	int j = 0;
	for (i = 0; i < arrSize; i++) {
		for (j = 0; j < arrSize; j++) {
			if (j == i) {
				continue;
			}
			if (arr[j] == 2 * arr[i]) {
				return true;
			}
		}
	}
	return false;
}
// 时间复杂度：O(n^2)，n为数组长度。
// 空间复杂度：O(1)。

// 方法2——排序+双指针
/*
思路：
在对数组进行排序后，用两个指针对数组进行遍历
先让一个指针p遍历数组的每一个元素，
当arr[p] > 0时，就使用q指针向后遍历，当出现arr[q] == 2 * arr[p]时，直接返回true即可，当出现arr[q] > 2 * arr[p]时候，
则说明数组中已不在可能2 * arr[p]，则让p后移一位，q保持原位。
当arr[p] < 0时，则需利用q指针向后遍历，当出现arr[q] == arr[p] / 2时，则直接返回true，当出现arr[q] > arr[p] / 2时候，
则说明数组中已不在可能arr[p] / 2，则让p后移一位，q保持原位。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个函数，比较两个整型数据的大小
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}
bool checkIfExist2(int* arr, int arrSize) {
	assert(arr);
	int p = 0;
	int q = 0;
	// 先对数组进行排序
	qsort(arr, arrSize, sizeof(int), cmp_int);
	while ((p < arrSize) && (q < arrSize)) {
		if (arr[p] > 0) {
			while (arr[q] < 2 * arr[p]) {
				q++;
				if (q >= arrSize) {
					break;
				}
			}
			if (q >= arrSize) {
				break;
			}
			if (arr[q] == 2 * arr[p]) {
				return true;
			}
			// else {
			// 	p++;
			// }
		}
		else if (arr[p] < 0) {
			while (arr[q] < arr[p] / 2.0) { // 要将arr[p] / 2 的运算转化成double型运算，防止向下取整所带来的数据不准确问题
				q++;
				if (q >= arrSize) {
					break;
				}
			}
			if (q >= arrSize) {
				break;
			}
			if (arr[q] == arr[p] / 2.0) {
				return true;
			}
			// else {
			// 	p++;
			// }
		}
		else {
			if (0 == arr[p + 1]) {
				return true;
			}
		}
		p++;

	}
	return false;
}

int main() {
	int arr[] = { 102,-592,457,802,98,-132,883,356,-857,461,-453,522,250,476,991,540,-852,-485,-637,999,-803,-691,-880,881,-584,750,-124,745,-909,-892,304,-814,868,665,50,-40,26,-242,-797,-360,-918,-741,88,-933,-93,360,-738,833,-191,563,449,840,806,-87,-950,508,74,-448,-815,-488,639,-334 };
	int len = sizeof(arr) / sizeof(arr[0]);
	printf("%d\n", checkIfExist2(arr, len));

	
	return 0;
}

